#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class node 
{
public:
    node(int n):val(n), next(NULL){}
    int val;
    node *next;
};

node *reverseRecursive(node *head)
{
   if (head->next == NULL) return head;
    node *rtn = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL; 
    return rtn;
}


int main(int argc, char **argv)
{
    int a[] = {1,2,3,4,5,6,7,8,9};
    node *dummy = new node(0);
    node *cur = dummy;
    for (int i = 0; i < sizeof(a)/sizeof(int); i++) {
        node *newnode = new node(a[i]);
        cur->next = newnode;
        cur = cur->next;
    }
    node *head = dummy->next;
    cur = head;
    while(cur) {
	cout << cur->val << " ";
	cur = cur->next;
    }
    cout << endl;

    head = reverseRecursive(head);
    cur = head;
    while(cur) {
	cout << cur->val << " ";
	cur = cur->next;
    }
    cout << endl;
}
